package com.data_structure_algorithm.sort;

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};

        shellSort(arr);


        System.out.println(Arrays.toString(arr));
/*
        int[] arrs = new int[10000000];
        for (int i = 0; i < 10000000; i++) {
            arrs[i] = (int) (Math.random() * 80000000);
        }
        String dateStart = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());
        System.out.println(dateStart);
        moveShellSort(arrs);
        String dateEnd = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss").format(new Date());

        System.out.println(dateEnd);*/

    }


    private static void sort(int[] arr) {
        //前值>=0,后值>=gap,gap是分界点


        //将数组分组（/2），得到组数，即步长，gap必须是正数，因为分组的组数不可能为负数，即gap==1是最后一次执行
        for (int gap = arr.length / 2; gap > 0;
             gap /= 2) { //每次大循环后都重新计算步长（一次大循环代表一轮，即数组内所有内组排序完毕）
            //i，从gap往后移动，每移动一次，对应下面for，比较该值和前面对应的值大小
            for (int i = gap; i < arr.length;
                 i++) { //比较完毕后向后推进，直到结尾
                int temp;
                //首次j即gap对应的值
                for (int j = i; //J代表每组内后面的值，即gap位置对应的值，gap不断变化，j随着改变
                     j >= gap;//从gap处向后移动（源于上层i++），每轮分别找gap对应位置的值和前面间隔gap的值比较，该值肯定在gap后面位置
                    //每次组内比较后，j都会移动到gap后移而对应的前面的值，前值随着gap后移，索引位置也在++（源于上层i++）
                     j -= gap) {//j -= gap代表前值，每次比较结束，根据gap不断向前找对应值，即gap位置对应的前值，一直循环到gap之前，说明前值走到头了（比较完了）
                    if (arr[j - gap] > arr[j]) {//前面的数>后面的数
                        temp = arr[j - gap];
                        arr[j - gap] = arr[j];
                        arr[j] = temp;
                    } else {
                        //无需交换,跳出本轮循环
                        break;
                    }


                }

            }
            //System.out.println(Arrays.toString(arr));
        }


    }


    public static void moveShellSort(int[] arr) {


        int h = 1;
        while (h <= arr.length / 3) {
            h = 3 * h + 1;
        }

        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {


            //后面的数
            for (int i = gap; i < arr.length; i++) {

                //假设后面的数需要插入到前面==>后小
                int insertIndex = i;
                int insertValue = arr[insertIndex];
                //开始循环
                while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
                    //i - gap >= 0 向前找越界
                    //insertValue < arr[insertIndex - gap]  当前插入的值比前面的值小，需要移动

                    //前面的值移动到后面位置
                    arr[insertIndex] = arr[insertIndex - gap];
                    //继续往前找
                    insertIndex -= gap;

                }

                //找到了
                arr[insertIndex] = insertValue;


            }

        }

    }


    public static void shellSort(int[] arr) {
        //定义gap,来确定间隔
        int h = 1;
        while (h <= arr.length / 3) {
            h = 3 * h + 1;
        }
        //定义最外侧分组
        for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
            //每组移动比较   gap不断向后移动和前面对应的数值比较
            for (int i = gap; i < arr.length; i++) {
                //gap向后移动，j也随之变化，j代表后面的值
                //j >= gap 说明gap对应的值正常向后移动
                //确定待插入的索引和对应数据
                int insertIndex = i;
                int insertValue = arr[insertIndex];
                //判断是否一次移动即可替换
                while (insertIndex - gap >= 0 && insertValue < arr[insertIndex - gap]) {
                    //该值不是要替换的数，继续向前找
                    //目前对应的值往后面移动
                    arr[insertIndex] = arr[insertIndex - gap];
                    insertIndex = insertIndex - gap; //向前移动
                }

                //找到合适的位置
                arr[insertIndex] = insertValue;

            }

        }
    }
}
